Недавно, при просмотре открытого собеседования от Яндекса и видео об алгоритмах с канала руководителя команды в Яндексе, заметил, что в оба сотрудника Яндекса говоря дополнительном выделении памяти под массив для результата, оценивают пространственную сложность по разному. В первом случае O(1), причем указывая на ошибку собеседуемого, во втором случае оценивает сложность, как O(n). Хотя для результата выполнения алгоритма выделяется место для нового массива в обоих случаях.

Если функция возвращает новый список, должен ли анализ пространственной сложности функции включать пространство, необходимое для вывода? Кажется, есть явные причины исключить входные данные из анализа, но менее ясно, следует ли исключать выходные данные. Имеет ли значение архитектура системы (например, многоленточная машина Тьюринга или современный компьютер с оперативной памятью)?

Поскольку большинство примеров анализа сложности, которые я видел, включают функции, которые либо ничего не возвращают (например, сортировка на месте), либо одно значение (например, вычисление, поиск), я не смог понять это, просто прочитав примеры.

Рассмотрим примеры реализации алгоритмов из видео. Все они используют вспомогательное и выходное пространство O(1), поэтому общая пространственная сложность меняется в зависимости от того, включаете ли вы выходное пространство или нет.

Привет алгоритма на Go их первого видео:

func sortedSquares(nums []int) []int {
    res := make([]int, len(nums))
    i := 0
    k := len(nums) - 1
    for j := len(nums) - 1; j >= 0; j-- {
        if abs(nums[k]) > abs(nums[i]) {
            res[j] = nums[k] * nums[k]
            k--
        } else {
            res[j] = nums[i] * nums[i]
            i++
        }
    }

    return res
}

func abs(x int) int {
    if x < 0 {
        return -x
    }

    return x
}

Пространственная сложность: O(1).

Пример реализации алгоритма на Go из 2 видео:

func modify(numbers []int) []int {
    var result []int
    for i := 0; i < len(numbers); i++ {
        result[i] = numbers[i] * numbers[i]
    }

    return result
}

Пространственная сложность: O(n).

На самом деле вопрос холиварный. Прочитав на stack exchange вопрос можно получить ответ почему именно. Здесь все же вопрос учитывать или не учитывать входное и выходное пространство. В данных алгоритмах если учитывать такую память, то пространственная сложность - O(n), если не учитывать, то есть учитывать только дополнительную память потребляемую алгоритмом, то сложность O(1).

Я думаю, что более распространенный анализ пространственной сложности фокусируется на объеме памяти, выделенной алгоритмом, а не на том, используется ли она в качестве вывода или нет. Если говорить об оценке потребляемой алгоритмом памяти, то можно говорить про какую-то абстрактную память. Это может быть как аллоцируемая дополнительная память, необходимая для корректно работы алгоритма, так и вся память, то есть входные и выходные данные. По этой причине, при оценки пространственной сложности алгоритма именно дополнительную память, потребляемую алгоритмом.